// 2025/3/23
// https://leetcode.cn/problems/find-median-from-data-stream/description/?envType=study-plan-v2&envId=top-100-liked
// 数据流的中位数

class MedianFinder {
    public:
        MedianFinder() 
            :size(0)
        {}
        
        void addNum(int num) {
            if(size % 2 == 0)
            {
                if(!right.empty() && num > right.top())
                {
                    left.emplace(right.top());
                    right.pop();
                    right.emplace(num);
                }
                else
                    left.emplace(num);
            }
            else
            {
                if(!left.empty() && num < left.top())
                {
                    right.emplace(left.top());
                    left.pop();
                    left.emplace(num);
                }
                else
                    right.emplace(num);
            }
            size++;
        }
        
        double findMedian() {
            assert(size);
            if(size % 2 == 0)
            {
                return (double)(left.top() + right.top()) / 2;
            }
            else
            {
                return left.top();
            }
        }
    
        priority_queue<int, deque<int>, less<int>> left;
        priority_queue<int, deque<int>, greater<int>> right;
        int size;
    };
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder* obj = new MedianFinder();
     * obj->addNum(num);
     * double param_2 = obj->findMedian();
     */